package LeetCode75;

/**
 * 1004. 最大连续1的个数 III
 * 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
 * 输出：6
 * 解释：[1,1,1,0,0,1,1,1,1,1,1]
 * 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
 * 示例 2：
 *
 * 输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
 * 输出：10
 * 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
 * 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * nums[i] 不是 0 就是 1
 * 0 <= k <= nums.length
 *
 * 打牌
 * 基本思路：题目提供k次机会把0翻转成1，相当于你手上有k张牌。
 * 右指针right 遍历数组，遇到0就“出牌”，手上的牌就少了。出到负数的时候，就要移动left 前进，遇到0才 “抽牌”，牌又多了
 * right和left之间的最长区间就是 连续1的最大个数
 */
public class T1004_最大连续1的个数III {

    //滑动窗口
    public static int longestOnes(int[] nums, int k) {

        //最大连续1的数量
        int max = 0;
        int left = 0;
        int right = 0;

        while (right < nums.length) {

            if (k > 0) {
                //移动右指针
                //如果当前数为0 使用一次翻转的机会
                if (nums[right] == 0) {
                    k--;
                }
                //向右走一步 并计算 最大值
                right++;
                max = Math.max(max, right - left);

            } else if (k == 0) {
                //可以尝试右指针继续走 但是遇到0要停下
                if (nums[right] != 0) {
                    right++;
                    max = Math.max(max, right - left);
                } else {
                    //无法继续向前 左指针前进
                    if (nums[left] == 0) {
                        k++;
                    }
                    left++;
                }

            }

        }

        return max;

    }

    public static void main(String[] args) {
     longestOnes(new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1},3);
    }
}
